package basic.basic_class01;

import basic.untils.ArrayTestUntil;

import java.util.Arrays;

/**
 * 快速排序
 */
public class Code_04_QuickSort {

    // 快排
    public static void quickSort(int[] arr) {
        if(arr.length > 1){
            sortHelp(arr,0,arr.length - 1);
        }
    }

    // 对指定位置元素进行排序，构建递归
    public static void sortHelp(int[] arr, int l, int r) {
        // 当arr排序范围有意义时才执行
        if(l < r){
            // 从l到r的位置随机找出一个值
            int temp = arr[l + (int)Math.random() * (r - l + 1)];
            // 将temp加入快排主程序，小于temp放左边，等于放中间，大于放右边
            int[] p = sortProcess(arr,l,r,temp);
            // 对余下的左边进行排序（左边一定都小于右边）
            sortHelp(arr,l,p[0]);
            // 对余下的右边进行排序
            sortHelp(arr,p[1],r);
        }
    }

    // 快排主函数
    private static int[] sortProcess(int[] arr, int l, int r, int temp) {
        // 定义左右指针，表明已经加入了多少
        int less = l - 1;
        int more = r + 1;
        // 如果l指针与more指针相交，结束循环
        while(l < more){
            if(arr[l] < temp){
                // 如果当前的元素小于temp，那么放l位置的元素，扔到前面去
                swap(arr,++less,l++);
            }else if(arr[l] > temp){
                // 如果当前的元素大于temp，那么放l位置的元素，扔到后面去
                swap(arr,--more,l);
            }else{
                // 如果等于，不操作，直接移动l指针
                l++;
            }
        }
        // 将左右两个边界返回
        return new int[]{less,more};
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //测试主方法
    public static void main(String[] args) {
        int testTime = 500000;  //测试次数
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = ArrayTestUntil.generateRandomArray(maxSize, maxValue);  //生成随机数组
            int[] arr1 = ArrayTestUntil.copyArray(arr);   //复制数组
            quickSort(arr);
            ArrayTestUntil.comparator(arr1);
            if (!ArrayTestUntil.isEquals(arr, arr1)) {
                System.out.println("手撸：" + Arrays.toString(arr));
                System.out.println("标准：" + Arrays.toString(arr1));
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking Fucked");
    }
}
